package com.javabasic.algorithm.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see [160. Intersection of Two Linked Lists](https://leetcode-cn.com/problems/intersection-of-two-linked-lists/)
 * @since Created by work on 2021/12/12 12:24 下午
 */
public class IntersectionOfTwoLinkedLists {

    /**
     * MAP+暴力解法
     * 直接表示否否有相同内存地址的对象，出现的第一个相同内存地址的对象即为相交节点
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Map<Integer, List<ListNode>> numToNodes = new HashMap<>(16);
        List<ListNode> listNodes;
        while (headA != null) {
            listNodes = numToNodes.getOrDefault(headA.val, new ArrayList<>());
            listNodes.add(headA);
            numToNodes.put(headA.val,listNodes);
            headA = headA.next;
        }
        while (headB != null) {
            listNodes = numToNodes.getOrDefault(headB.val, new ArrayList<>());
            if (listNodes.contains(headB)) {
                return headB;
            }
            listNodes.add(headB);
            numToNodes.put(headB.val,listNodes);
            headB = headB.next;
        }
        return null;

    }


    /**
     * 思维逻辑解法：
     * 用两个指针同时从两个链表的头节点出发，同时走长度为：两个链表长度的总和（第一个链表尾节点的下一步为第二个链表的头，第二个链表尾节点的下一步为第一个链表的头）
     * 如果此时两个指针指向相等，那么即为相交的其实节点，否则就是不想交，且此时两个指针的下一跳均为空指针
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        ListNode indexA = headA, indexB = headB;
        while (indexA != indexB) {
            // 如果两个指针的下一跳均为空指针的话那么这两个链表一定不想交
            if (indexA.next == null && indexB.next == null) {
                return null;
            }
            indexA = (indexA.next == null) ? headB : indexA.next;
            indexB = (indexB.next == null) ? headA : indexB.next;
        }
        return indexA;
    }


    /**
     * 转为循环链表+双指针
     * 1. 将两个链表合成一个链表
     * 2. 判断链表是否有环
     * 3. 查找相交节点
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode3(ListNode headA, ListNode headB) {
        // 将两个链表合成一个链表
        ListNode indexA = headA, indexB, tailA;
        while (indexA.next != null) {
            indexA = indexA.next;
        }
        indexA.next = headB;
        tailA = indexA;
        indexA = headA;
        indexB = headA;

        // 判断链表是否有环
        boolean cycle = false;
        do {
            indexA = indexA.next;
            if (indexB.next != null) {
                indexB = indexB.next.next;
            } else {
                break;
            }
            if (indexA == indexB) {
                cycle = true;
                break;
            }
            // 如果有节点指向了空节点，就表示这个链表是一个五无环结构，直接break;
            if (indexA == null || indexB == null) {
                break;
            }
        } while (true);

        // 如果无环直接返回
        if (cycle == false) {
            tailA.next = null;
            return null;
        }


        // 查找相交节点
        indexA = headA;
        while (indexA != indexB) {
            indexA = indexA.next;
            indexB = indexB.next;
        }
        tailA.next = null;
        return indexA;
    }


}
